#include <stdio.h>
#include <stdlib.h>

typedef struct searchTree
{
    int num;
    struct searchTree * lchild;
    struct searchTree * rchild;
}SearchTree;

SearchTree * initSearchTree();
void insert(SearchTree * root, int num);
int update(SearchTree * root, int old, int new);
int delete(SearchTree * root, int value);
void display(SearchTree * root);

int main(){
    SearchTree * root = initSearchTree();
    insert(root,6);
    insert(root,3);
    insert(root,5);
    insert(root,2);
    insert(root,9);
    display(root);
    delete(root,2);
    update(root,5,33);
    display(root);
    return 0 ;
}
int delete(SearchTree * root, int value){
	SearchTree *temp;
	SearchTree *front;
	temp = root;
	front = root;
	while(temp){
		if(temp->num==value){

			if(temp==front){
				return 0;
			}else if(temp->lchild==NULL&&temp->rchild==NULL){
				if(front->lchild == temp){
					front->lchild = NULL;
					free(temp);
					return 1;
				}else{
					front->rchild = NULL;
					free(temp);
					return 1;
				}
			}else if(temp->lchild==NULL){
				if(front->lchild==temp){
					front->lchild = temp->rchild;
					free(temp);
					return 1;
				}else{
					front->rchild = temp->rchild;
					free(temp);
					return 1;
				}
			}else if(temp->rchild==NULL){
				if(front->lchild ==temp){
					front->lchild = temp->lchild;
					free(temp);
					return 1;
				}else{
					front->rchild = temp->lchild;
					free(temp);
					return 1;
				}
			
			}else{
				SearchTree * t;
				SearchTree * pt;
				t = temp;
				pt = temp;
				t = temp->rchild;
				while(t->lchild){
					pt = t;
					t = t->lchild;
				}
				if(front->lchild == temp){
					front->lchild = t;
				}else{
					front->rchild = t;

				
				}
				t->lchild = temp->lchild;
				t->rchild = temp->rchild;
				free(temp);
				pt->lchild = NULL;
				return 1;
			
			}
		
		}else if(temp->num > value){
			front = temp;
			temp=temp->lchild;
		}else{
			front = temp;
			temp=temp->rchild;
		}
	}
	return -1;
}
int update(SearchTree * root,int old, int new){
	int res = delete(root,old);
	if(res == 1){
		insert(root,new);
		return 1;
	}
	return 0;
}
void display(SearchTree * root){
    SearchTree * q[100];
	q[0] = root;
	int front = 0;
	int rear = 1;
	while(front < rear){
		printf("%d ",q[front]->num);
		if(q[front]->lchild)
		{
			q[rear++] = q[front]->lchild;
		}	
		if(q[front]->rchild){
			q[rear++] = q[front]->rchild;
		}

		++front;
	}
	printf("\n");
}

void insert(SearchTree * root, int num){
    SearchTree * temp = root;
    if(temp->num == -1){
        temp -> num = num;
    }else{
        while (temp)
        {
            if(num > temp->num && temp->rchild){
                temp = temp->rchild;
            }else if(num <= temp->num && temp->lchild){
                temp = temp->lchild;
            }else{
                SearchTree *p = (SearchTree*)malloc(sizeof(SearchTree));
                p->lchild = NULL;
                p->rchild = NULL;
                p->num = num;
                if(num > temp->num){
                    temp->rchild = p;
                }else{
                    temp->lchild = p;
                }
                break;
            }
        }

        
        
    }
}

SearchTree * initSearchTree(){

    SearchTree * root = (SearchTree*)malloc(sizeof(SearchTree));
    root->lchild = NULL;
    root->rchild = NULL;
    root->num = -1;

    return root;
}
